package com.company.arithmetic;

import java.util.*;

/**
 * Created by v on 17-6-7.
 */
public class TSP {
    private static class Node{
        //还没有去的结点
        List<Integer> list;
        //是否已经完成了
        boolean solution;
        //出发结点
        int begin;
        //已经消耗的权值
        int bound;

        public Node(List<Integer> list,boolean solution,int begin,int bound){
            this.list=list;
            this.solution=solution;
            this.begin=begin;
            this.bound=bound;
        }
    }

    //优先队列
    private static Queue<Node> queue= new PriorityQueue<>(((o1, o2) ->((Integer)o1.bound).compareTo(o2.bound)));

    //最大值，相当于无穷大
    private static final int MAX=Integer.MAX_VALUE/2;

    //原始矩阵
    private static int[][] matrix;

    //主要驱动函数
    private static int solve(){
        List<Integer> list=new LinkedList<>();
        for(int i=1;i<matrix.length;i++){
            list.add(i);
        }
        Node node=new Node(list,false,0,0);
        queue.offer(node);

        while (!queue.isEmpty()){
            node=queue.poll();
            //如果队列弹出了一个已经到达终点的节点，那么它的耗费就是最大耗费了。
            if(node.solution){
                return node.bound;
            }

            list=node.list;
            //如果已经走完所有的点了，则加上回去0号点的耗费，再次载入到优先队列
            if(list.size()==0){
                node.bound=node.bound+matrix[node.begin][0];
                node.solution=true;
                queue.offer(node);
                continue;
            }

            //对于没有走完的节点，对每个节点创建一个新的孩子节点并放入优先队列
            for(int end:list){
                List<Integer> list1=clone(list,end);
                int bound=node.bound+matrix[node.begin][end];
                Node node1=new Node(list1,false,end,bound);
                queue.offer(node1);
            }
        }

        return -1;
    }

    private static List<Integer> clone(List<Integer> list,int current){
        List list1=new LinkedList();
        for(int i=0;i<list.size();i++){
            if(list.get(i)!=current){
                list1.add(list.get(i));
            }
        }

        return list1;
    }

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);

        System.out.println("请输入矩阵大小n:");

        int n=input.nextInt();
        System.out.println("请输入商旅问题的原始矩阵，在无穷大的地方输入-1:");
        matrix=new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                matrix[i][j]=input.nextInt();

                if(matrix[i][j]==-1){
                    matrix[i][j]=MAX;
                }
            }
        }

        for(int i=0;i<n;i++){
            matrix[i][i]=MAX;
        }

        System.out.println("所消耗的bound为："+solve());
    }
}
